#include <stdio.h>
#include <stdlib.h>

#define NUM 10
typedef struct node
{
    int data;          // 存数据
    struct node *next; // 存指针
} Hash;

typedef struct
{
    int num;
    Hash *hash[];
} hash_table;

hash_table *hash_init(int num)
{
    hash_table *table = calloc(1, sizeof(int) + sizeof(Hash *) * num);
    if (table == NULL)
    {
        perror("hash init failed");
        return NULL;
    }
    table->num = num;

    Hash *tmp;
    for (int i = 0; i < num; i++)
    {
        tmp = calloc(1, sizeof(Hash));
        if (tmp)
        {
            tmp->next = NULL;
            tmp->data = 0;
            table->hash[i] = tmp;
        }
        else
        {
            perror("malloc Hash failed");
            return NULL;
        }
    }

    return table;
}

Hash *hash_insert(hash_table *table, int data)
{
    int key = data % table->num;
    Hash *index = table->hash[key];

    Hash *new = malloc(sizeof(Hash));
    if (new == NULL)
    {
        perror("hash_insert data failed");
        return NULL;
    }
    new->data = data;
    new->next = index->next;
    index->next = new;

    return new;
}

int hash_show(hash_table *table)
{
    for (int i = 0; i < table->num; i++)
    {
        Hash *index = table->hash[i];
        printf("index[%d]: ", i);
        while (index->next != NULL)
        {
            printf(" %d ", index->next->data);
            index = index->next;
        }
        printf("\n");
    }

    return 0;
}

int hash_search(hash_table *table, int data)
{
    int key = data % table->num;
    Hash *index = table->hash[key];
    while (index->next != NULL)
    {
        if (index->next->data == data)
        {
            printf("find %d in key[%d]\n", data, key);
            return 1;
        }
        index = index->next;
    }

    return 0;
}

void hash_free(hash_table *table)
{
    for (int i = 0; i < table->num; i++)
    {
        Hash *index = table->hash[i];
        while (index->next != NULL)
        {
            Hash *tmp = index->next;
            index->next = tmp->next;
            free(tmp);
        }
        free(index);
    }
    free(table);
}

int main(void)
{
    hash_table *table = hash_init(NUM);
    int a[] = {11, 31, 45, 67, 89, 43, 98, 92, 73, 82};
    int a_len = sizeof(a) / sizeof(a[0]);
    int i;
    for (i = 0; i < a_len; i++)
    {
        hash_insert(table, a[i]);
    }
    hash_show(table);

    int b[] = {11, 55, 45, 66, 89, 77, 98, 88, 73, 99};
    int b_len = sizeof(b) / sizeof(b[0]);
    for (i = 0; i < b_len; i++)
    {
        hash_search(table, b[i]);
    }

    hash_free(table);

    return 0;
}
